package code.classic150on2025;

import utils.ListNode;

import java.util.HashMap;
import java.util.Map;

public class TheList {
    // 2. 两数相加
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ans = new ListNode();
        ListNode prev = null;
        ListNode head = ans;
        int adding = 0;
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val + adding;
            ans.val = sum % 10;
            ans.next = new ListNode();
            prev = ans;
            ans = ans.next;
            l1 = l1.next;
            l2 = l2.next;
            adding = sum / 10;
        }
        while (l1 != null) {
            int sum = l1.val + adding;
            ans.val = sum % 10;
            ans.next = new ListNode();
            prev = ans;
            ans = ans.next;
            l1 = l1.next;
            adding = sum / 10;
        }
        while (l2 != null) {
            int sum = l2.val + adding;
            ans.val = sum % 10;
            ans.next = new ListNode();
            prev = ans;
            ans = ans.next;
            l2 = l2.next;
            adding = sum / 10;
        }
        if (adding != 0) {
            ans.val = adding;
            ans.next = null;
        } else {
            if (prev != null) {
                prev.next = null;
            }
        }
        return head;
    }

    // 138. 随机链表的复制
    public NodeRandom copyRandomList(NodeRandom head) {
        if (head == null)
            return null;
        NodeRandom node = head;
        Map<NodeRandom, NodeRandom> map = new HashMap<>();
        while (node != null) {
            map.put(node, new NodeRandom(node.val));
            node = node.next;
        }
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        return map.get(head);
    }

    // 92. 反转链表 II
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode pre = new ListNode();
        pre.next = head;
        ListNode next = pre;
        ListNode headPre = pre;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        for (int i = 0; i < right + 1; i++) {
            next = next.next;
        }
        ListNode now = pre.next, nowPre = null;
        ListNode finallyLast = now;
        while (now != next) {
            ListNode nowNext = now.next;
            now.next = nowPre;
            nowPre = now;
            now = nowNext;
        }
        pre.next = nowPre;
        finallyLast.next = next;
        return headPre.next;
    }

    // 25. K 个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode headPre = new ListNode();
        headPre.next = head;
        int count = 0;
        ListNode node = head;
        ListNode pre = headPre;
        ListNode leftLast = null, nowFirst = null, nextFirst = null;
        while (node != null) {
            count++;
            if (count == 1) {
                leftLast = pre;
                nowFirst = node;
            }
            if (count == k) {
                nextFirst = node.next;
                // reverse
                ListNode pos = nowFirst, prePos = null;
                while (pos != nextFirst) {
                    ListNode posNext = pos.next;
                    pos.next = prePos;
                    prePos = pos;
                    pos = posNext;
                }
                leftLast.next = prePos;
                nowFirst.next = nextFirst;
                // reset
                count = 0;
                pre = nowFirst;
                node = nextFirst;
            } else {
                pre = node;
                node = node.next;
            }
        }
        return headPre.next;
    }

    // 19. 删除链表的倒数第 N 个结点
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode first = preHead;
        for (int i = 0; i < n; i++) {
            first = first.next;
        }
        ListNode node = preHead;
        while (first.next != null) {
            first = first.next;
            node = node.next;
        }
        if (node.next == head) {
            return head.next;
        } else {
            node.next = node.next.next;
            return head;
        }
    }

    // 82. 删除排序链表中的重复元素 II
    public ListNode deleteDuplicates(ListNode head) {
        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode node = preHead;
        while (node != null) {
            while (node.next != null && node.next.next != null && node.next.val == node.next.next.val) {
                int deleteVal = node.next.val;
                ListNode temp = node.next;
                while (temp != null && temp.val == deleteVal) {
                    temp = temp.next;
                }
                node.next = temp;
            }
            node = node.next;
        }
        return preHead.next;
    }

    // 61. 旋转链表
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null) return null;

        int count = 0;
        ListNode node = head;
        while (node != null) {
            count++;
            node = node.next;
        }
        k %= count;
        if (k == 0)
            return head;

        ListNode preHead = new ListNode();
        preHead.next = head;
        ListNode split = preHead;
        for (int i = 0; i < count - k; i++) {
            split = split.next;
        }
        ListNode newFirst = split.next;
        ListNode newLast = newFirst;
        while (newLast.next != null) {
            newLast = newLast.next;
        }
        newLast.next = head;
        split.next = null;
        return newFirst;
    }

    // 86. 分隔链表
    public ListNode partition(ListNode head, int x) {
        ListNode node = head;
        ListNode small = new ListNode(), s = small;
        ListNode big = new ListNode(), b = big;
        while (node != null) {
            if (node.val < x) {
                s.next = node;
                node = node.next;
                s = s.next;
                s.next = null;
            } else {
                b.next = node;
                node = node.next;
                b = b.next;
                b.next = null;
            }
        }
        s.next = big.next;
        return small.next;
    }

    // 146. LRU 缓存
    class LRUNode {
        int val;
        int key;
        LRUNode next;
        LRUNode prev;
        public LRUNode() {}
    }

    class LRUCache {
        Map<Integer, LRUNode> map;
        LRUNode head, tail;
        int c;
        int count;

        public LRUCache(int capacity) {
            c = capacity;
            map = new HashMap<>();
            head = new LRUNode();
            tail = new LRUNode();
            head.next = tail;
            tail.prev = head;
            count = 0;
        }

        public int get(int key) {
            if (!map.containsKey(key))
                return -1;
            LRUNode node = map.get(key);
            LRUNode preNode = node.prev;
            LRUNode nextNode = node.next;
            preNode.next = nextNode;
            nextNode.prev = preNode;
            LRUNode headNext = head.next;
            head.next = node;
            node.prev = head;
            node.next = headNext;
            headNext.prev = node;
            return node.val;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                LRUNode node = map.get(key);
                node.val = value;
                LRUNode preNode = node.prev;
                LRUNode nextNode = node.next;
                preNode.next = nextNode;
                nextNode.prev = preNode;
                LRUNode headNext = head.next;
                head.next = node;
                node.prev = head;
                node.next = headNext;
                headNext.prev = node;
            } else {
                LRUNode newNode = new LRUNode();
                newNode.val = value;
                newNode.key = key;
                LRUNode headNext = head.next;
                head.next = newNode;
                newNode.prev = head;
                newNode.next = headNext;
                headNext.prev = newNode;
                if (c > count) {
                    count++;
                } else {
                    LRUNode deleteNode = tail.prev;
                    LRUNode deletePre = deleteNode.prev;
                    deletePre.next = tail;
                    tail.prev = deletePre;
                    map.remove(deleteNode.key);
                }
                map.put(key, newNode);
            }
        }
    }
}

class NodeRandom {
    int val;
    NodeRandom next;
    NodeRandom random;
    public NodeRandom(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}